/*
 * @lc app=leetcode.cn id=2096 lang=typescript
 *
 * [2096] 从二叉树一个节点到另一个节点每一步的方向
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function getDirections(root: TreeNode | null, startValue: number, destValue: number): string {
  let sPath = '';
  let dPath = '';
  const path = new Array<string>(100);
  const getPathString = (node: TreeNode | null, path: string[] = [], deep: number) => {
    path[deep] = '';
    if (node === null) return;

    if (node.val === startValue) sPath = path.slice(0, deep).join('');
    if (node.val === destValue) dPath = path.slice(0, deep).join('');
    path[deep] = 'L';
    getPathString(node.left, path, deep + 1);
    path[deep] = 'R';
    getPathString(node.right, path, deep + 1);
  };

  // 计算起点和终点的字符串路径
  getPathString(root, path, 0);

  let i = 0;
  // 两个路径相同的前缀代表二者的祖父节点位置
  while (sPath[i] && sPath[i] === dPath[i]) i++;
  // 将相同路径去除后，剩下的就是一条最短路径
  sPath = sPath.slice(i);
  dPath = dPath.slice(i);

  // 将起始节点的路径字符都转成 U
  let sPathRes = '';
  for (const _ of sPath) {
    sPathRes += 'U';
  }
  return sPathRes + dPath;
}
// @lc code=end
